#include <iostream>
#include <numeric>
#include <cstring>

using namespace std;

#define MAX 1024

int dp[MAX][MAX];
int stones[MAX];

int Least_Effort(int n)
{
    int i, j, k;
    for (i = 0; i < n; i++)
        dp[i][i] = 0;

    for (i = n - 1; i >= 0; i--)
    {
        // 往后k步
        for (k = 1; k < n - i; k++)
        {
            j = i + k;                                           // j为目标地址
            int sum = accumulate(&stones[i], &stones[j + 1], 0); // 左闭右开
            for (int L = i; L < j; L++)
                dp[i][j] = min(dp[i][j], dp[i][L] + dp[L + 1][j] + sum);
        }
    }

    return dp[0][n - 1];
}

int main()
{
    int n;
    while (true)
    {
        memset(dp, 0x3F, sizeof(dp));

        memset(stones, 0, sizeof(stones));
        cout << "请输入石子数n：";
        cin >> n;

        cout << "请输入" << n << "堆石子的数量：\n";
        for (int i = 0; i < n; i++)
            cin >> stones[i];

        cout << "合并" << n << "堆石子，最小代价为：" << Least_Effort(n) << endl;
    }
}

/*
3
1 2 3

7
13 7 8 16 21 4 18
*/